home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 7: Sunsite / Linux Cubed Series 7 - Sunsite Vol 1.iso / system / network / file-tra / rdist-6.1 / rdist-6 / rdist-6.1.0-linuxpl2 / src / regex.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-01-01  |  9.8 KB  |  435 lines
  1. /*
  2.  * Copyright (c) 1983 Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #if !defined(lint)
  35. static char RCSid[] =
  36. "$Id: regex.c,v 6.2 1993/01/01 01:17:04 mcooper Exp mcooper $";
  37.  
  38. static char sccsid[] = "@(#)regex.c    5.2 (Berkeley) 3/9/86";
  39.  
  40. static char copyright[] =
  41. "@(#) Copyright (c) 1983 Regents of the University of California.\n\
  42.  All rights reserved.\n";
  43. #endif /* not lint */
  44.  
  45. /*
  46.  * routines to do regular expression matching
  47.  *
  48.  * Entry points:
  49.  *
  50.  *    re_comp(s)
  51.  *        char *s;
  52.  *     ... returns 0 if the string s was compiled successfully,
  53.  *             a pointer to an error message otherwise.
  54.  *         If passed 0 or a null string returns without changing
  55.  *           the currently compiled re (see note 11 below).
  56.  *
  57.  *    re_exec(s)
  58.  *        char *s;
  59.  *     ... returns 1 if the string s matches the last compiled regular
  60.  *               expression, 
  61.  *             0 if the string s failed to match the last compiled
  62.  *               regular expression, and
  63.  *            -1 if the compiled regular expression was invalid 
  64.  *               (indicating an internal error).
  65.  *
  66.  * The strings passed to both re_comp and re_exec may have trailing or
  67.  * embedded newline characters; they are terminated by nulls.
  68.  *
  69.  * The identity of the author of these routines is lost in antiquity;
  70.  * this is essentially the same as the re code in the original V6 ed.
  71.  *
  72.  * The regular expressions recognized are described below. This description
  73.  * is essentially the same as that for ed.
  74.  *
  75.  *    A regular expression specifies a set of strings of characters.
  76.  *    A member of this set of strings is said to be matched by
  77.  *    the regular expression.  In the following specification for
  78.  *    regular expressions the word `character' means any character but NUL.
  79.  *
  80.  *    1.  Any character except a special character matches itself.
  81.  *        Special characters are the regular expression delimiter plus
  82.  *        \ [ . and sometimes ^ * $.
  83.  *    2.  A . matches any character.
  84.  *    3.  A \ followed by any character except a digit or ( )
  85.  *        matches that character.
  86.  *    4.  A nonempty string s bracketed [s] (or [^s]) matches any
  87.  *        character in (or not in) s. In s, \ has no special meaning,
  88.  *        and ] may only appear as the first letter. A substring 
  89.  *        a-b, with a and b in ascending ASCII order, stands for
  90.  *        the inclusive range of ASCII characters.
  91.  *    5.  A regular expression of form 1-4 followed by * matches a
  92.  *        sequence of 0 or more matches of the regular expression.
  93.  *    6.  A regular expression, x, of form 1-8, bracketed \(x\)
  94.  *        matches what x matches.
  95.  *    7.  A \ followed by a digit n matches a copy of the string that the
  96.  *        bracketed regular expression beginning with the nth \( matched.
  97.  *    8.  A regular expression of form 1-8, x, followed by a regular
  98.  *        expression of form 1-7, y matches a match for x followed by
  99.  *        a match for y, with the x match being as long as possible
  100.  *        while still permitting a y match.
  101.  *    9.  A regular expression of form 1-8 preceded by ^ (or followed
  102.  *        by $), is constrained to matches that begin at the left
  103.  *        (or end at the right) end of a line.
  104.  *    10. A regular expression of form 1-9 picks out the longest among
  105.  *        the leftmost matches in a line.
  106.  *    11. An empty regular expression stands for a copy of the last
  107.  *        regular expression encountered.
  108.  */
  109.  
  110. /*
  111.  * constants for re's
  112.  */
  113. #define    CBRA    1
  114. #define    CCHR    2
  115. #define    CDOT    4
  116. #define    CCL    6
  117. #define    NCCL    8
  118. #define    CDOL    10
  119. #define    CEOF    11
  120. #define    CKET    12
  121. #define    CBACK    18
  122.  
  123. #define    CSTAR    01
  124.  
  125. #define    ESIZE    512
  126. #define    NBRA    9
  127.  
  128. static    char    expbuf[ESIZE], *braslist[NBRA], *braelist[NBRA];
  129. static    char    circf;
  130. static    int    advance();
  131.  
  132. /*
  133.  * compile the regular expression argument into a dfa
  134.  */
  135. char *
  136. re_comp(sp)
  137.     register char    *sp;
  138. {
  139.     register int    c;
  140.     register char    *ep = expbuf;
  141.     int    cclcnt, numbra = 0;
  142.     char    *lastep = 0;
  143.     char    bracket[NBRA];
  144.     char    *bracketp = &bracket[0];
  145.     static    char    *retoolong = "Regular expression too long";
  146.  
  147. #define    comerr(msg) {expbuf[0] = 0; numbra = 0; return(msg); }
  148.  
  149.     if (sp == 0 || *sp == '\0') {
  150.         if (*ep == 0)
  151.             return("No previous regular expression");
  152.         return(0);
  153.     }
  154.     if (*sp == '^') {
  155.         circf = 1;
  156.         sp++;
  157.     }
  158.     else
  159.         circf = 0;
  160.     for (;;) {
  161.         if (ep >= &expbuf[ESIZE])
  162.             comerr(retoolong);
  163.         if ((c = *sp++) == '\0') {
  164.             if (bracketp != bracket)
  165.                 comerr("unmatched \\(");
  166.             *ep++ = CEOF;
  167.             *ep++ = 0;
  168.             return(0);
  169.         }
  170.         if (c != '*')
  171.             lastep = ep;
  172.         switch (c) {
  173.  
  174.         case '.':
  175.             *ep++ = CDOT;
  176.             continue;
  177.  
  178.         case '*':
  179.             if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
  180.                 goto defchar;
  181.             *lastep |= CSTAR;
  182.             continue;
  183.  
  184.         case '$':
  185.             if (*sp != '\0')
  186.                 goto defchar;
  187.             *ep++ = CDOL;
  188.             continue;
  189.  
  190.         case '[':
  191.             *ep++ = CCL;
  192.             *ep++ = 0;
  193.             cclcnt = 1;
  194.             if ((c = *sp++) == '^') {
  195.                 c = *sp++;
  196.                 ep[-2] = NCCL;
  197.             }
  198.             do {
  199.                 if (c == '\0')
  200.                     comerr("missing ]");
  201.                 if (c == '-' && ep [-1] != 0) {
  202.                     if ((c = *sp++) == ']') {
  203.                         *ep++ = '-';
  204.                         cclcnt++;
  205.                         break;
  206.                     }
  207.                     while (ep[-1] < c) {
  208.                         *ep = ep[-1] + 1;
  209.                         ep++;
  210.                         cclcnt++;
  211.                         if (ep >= &expbuf[ESIZE])
  212.                             comerr(retoolong);
  213.                     }
  214.                 }
  215.                 *ep++ = c;
  216.                 cclcnt++;
  217.                 if (ep >= &expbuf[ESIZE])
  218.                     comerr(retoolong);
  219.             } while ((c = *sp++) != ']');
  220.             lastep[1] = cclcnt;
  221.             continue;
  222.  
  223.         case '\\':
  224.             if ((c = *sp++) == '(') {
  225.                 if (numbra >= NBRA)
  226.                     comerr("too many \\(\\) pairs");
  227.                 *bracketp++ = numbra;
  228.                 *ep++ = CBRA;
  229.                 *ep++ = numbra++;
  230.                 continue;
  231.             }
  232.             if (c == ')') {
  233.                 if (bracketp <= bracket)
  234.                     comerr("unmatched \\)");
  235.                 *ep++ = CKET;
  236.                 *ep++ = *--bracketp;
  237.                 continue;
  238.             }
  239.             if (c >= '1' && c < ('1' + NBRA)) {
  240.                 *ep++ = CBACK;
  241.                 *ep++ = c - '1';
  242.                 continue;
  243.             }
  244.             *ep++ = CCHR;
  245.             *ep++ = c;
  246.             continue;
  247.  
  248.         defchar:
  249.         default:
  250.             *ep++ = CCHR;
  251.             *ep++ = c;
  252.         }
  253.     }
  254. }
  255.  
  256. /* 
  257.  * match the argument string against the compiled re
  258.  */
  259. int
  260. re_exec(p1)
  261.     register char    *p1;
  262. {
  263.     register char    *p2 = expbuf;
  264.     register int    c;
  265.     int    rv;
  266.  
  267.     for (c = 0; c < NBRA; c++) {
  268.         braslist[c] = 0;
  269.         braelist[c] = 0;
  270.     }
  271.     if (circf)
  272.         return((advance(p1, p2)));
  273.     /*
  274.      * fast check for first character
  275.      */
  276.     if (*p2 == CCHR) {
  277.         c = p2[1];
  278.         do {
  279.             if (*p1 != c)
  280.                 continue;
  281.             if (rv = advance(p1, p2))
  282.                 return(rv);
  283.         } while (*p1++);
  284.         return(0);
  285.     }
  286.     /*
  287.      * regular algorithm
  288.      */
  289.     do
  290.         if (rv = advance(p1, p2))
  291.             return(rv);
  292.     while (*p1++);
  293.     return(0);
  294. }
  295.  
  296. /* 
  297.  * try to match the next thing in the dfa
  298.  */
  299. static    int
  300. advance(lp, ep)
  301.     register char    *lp, *ep;
  302. {
  303.     register char    *curlp;
  304.     int    ct, i;
  305.     int    rv;
  306.  
  307.     for (;;)
  308.         switch (*ep++) {
  309.  
  310.         case CCHR:
  311.             if (*ep++ == *lp++)
  312.                 continue;
  313.             return(0);
  314.  
  315.         case CDOT:
  316.             if (*lp++)
  317.                 continue;
  318.             return(0);
  319.  
  320.         case CDOL:
  321.             if (*lp == '\0')
  322.                 continue;
  323.             return(0);
  324.  
  325.         case CEOF:
  326.             return(1);
  327.  
  328.         case CCL:
  329.             if (cclass(ep, *lp++, 1)) {
  330.                 ep += *ep;
  331.                 continue;
  332.             }
  333.             return(0);
  334.  
  335.         case NCCL:
  336.             if (cclass(ep, *lp++, 0)) {
  337.                 ep += *ep;
  338.                 continue;
  339.             }
  340.             return(0);
  341.  
  342.         case CBRA:
  343.             braslist[*ep++] = lp;
  344.             continue;
  345.  
  346.         case CKET:
  347.             braelist[*ep++] = lp;
  348.             continue;
  349.  
  350.         case CBACK:
  351.             if (braelist[i = *ep++] == 0)
  352.                 return(-1);
  353.             if (backref(i, lp)) {
  354.                 lp += braelist[i] - braslist[i];
  355.                 continue;
  356.             }
  357.             return(0);
  358.  
  359.         case CBACK|CSTAR:
  360.             if (braelist[i = *ep++] == 0)
  361.                 return(-1);
  362.             curlp = lp;
  363.             ct = braelist[i] - braslist[i];
  364.             while (backref(i, lp))
  365.                 lp += ct;
  366.             while (lp >= curlp) {
  367.                 if (rv = advance(lp, ep))
  368.                     return(rv);
  369.                 lp -= ct;
  370.             }
  371.             continue;
  372.  
  373.         case CDOT|CSTAR:
  374.             curlp = lp;
  375.             while (*lp++)
  376.                 ;
  377.             goto star;
  378.  
  379.         case CCHR|CSTAR:
  380.             curlp = lp;
  381.             while (*lp++ == *ep)
  382.                 ;
  383.             ep++;
  384.             goto star;
  385.  
  386.         case CCL|CSTAR:
  387.         case NCCL|CSTAR:
  388.             curlp = lp;
  389.             while (cclass(ep, *lp++, ep[-1] == (CCL|CSTAR)))
  390.                 ;
  391.             ep += *ep;
  392.             goto star;
  393.  
  394.         star:
  395.             do {
  396.                 lp--;
  397.                 if (rv = advance(lp, ep))
  398.                     return(rv);
  399.             } while (lp > curlp);
  400.             return(0);
  401.  
  402.         default:
  403.             return(-1);
  404.         }
  405. }
  406.  
  407. backref(i, lp)
  408.     register int    i;
  409.     register char    *lp;
  410. {
  411.     register char    *bp;
  412.  
  413.     bp = braslist[i];
  414.     while (*bp++ == *lp++)
  415.         if (bp >= braelist[i])
  416.             return(1);
  417.     return(0);
  418. }
  419.  
  420. int
  421. cclass(set, c, af)
  422.     register char    *set, c;
  423.     int    af;
  424. {
  425.     register int    n;
  426.  
  427.     if (c == 0)
  428.         return(0);
  429.     n = *set++;
  430.     while (--n)
  431.         if (*set++ == c)
  432.             return(af);
  433.     return(! af);
  434. }
  435.